package mid.class5;

import cn.hutool.core.util.ArrayUtil;

import java.util.Arrays;


/**
 * 使用链式前向星-构建图
 * <p>
 * [1,3]
 */
public class Code02_Graph {


    public static void main(String[] args) {
        int[][] nums = new int[][]{
                {1, 3, 6},
                {4, 3, 4},
                {2, 4, 2},
                {1, 2, 7},
                {2, 3, 5},
                {3, 1, 1}
        };
        int n = 4;
        Code02_Graph code02Graph = new Code02_Graph(n);
        code02Graph.createGraph1(nums);
//        ArrayUtils.printMatrixArr(new int[][]{head, to, next, weight});
        System.out.println("head:\t" + ArrayUtil.toString(head));
        System.out.println("to:\t\t" + ArrayUtil.toString(to));
        System.out.println("next:\t" + ArrayUtil.toString(next));
        System.out.println("weight:\t" + ArrayUtil.toString(weight));
        code02Graph.printGraph(n);

    }

    public static int MAXN = 11;
    public static int MAXM = 21;

    /**
     * head数组[0,1,2,3,4],下标表示点的编号
     * 位置的值不为0时，表示其边的编号
     */
    public static int[] head = new int[MAXN];

    /**
     * 边的编号，下一条边的编号
     */
    public static int[] next = new int[MAXM];

    /**
     * 边的编号，去往的点
     */
    public static int[] to = new int[MAXM];

    public static int[] weight = new int[MAXM];
    /**
     * 默认为:1,每来一条边都cnt++
     */
    public static int cnt;

    public Code02_Graph(int n) {
        this.cnt = 1;
        Arrays.fill(head, 1, n + 1, 0);
    }

    /**
     * 有向图
     */
    public static void createGraph1(int[][] edges) {
        // 链式前向星建图
        for (int[] edge : edges) {
            addEdge(edge[0], edge[1], edge[2]);
//            System.out.println(edge[0] + "\t" + edge[1] + "\t" + edge[2]);
//            System.out.println("head:" + ArrayUtil.toString(head));
//            System.out.println("next:" + ArrayUtil.toString(next));
//            System.out.println("to:" + ArrayUtil.toString(to));
//            System.out.println("weight:" + ArrayUtil.toString(weight));
        }
    }

    /**
     * 无向图
     */
    public static void createGraph2(int[][] edges) {
        // 链式前向星建图
        for (int[] edge : edges) {
            addEdge(edge[0], edge[1], edge[2]);
            addEdge(edge[1], edge[0], edge[2]);
        }
    }

    // 链式前向星加边
    public static void addEdge(int u, int v, int w) {
        // u -> v , 边权重是w
        next[cnt] = head[u];  // 将当前边的下一个节点设置为原来u的第一条边
        to[cnt] = v; // 边的终点是v
        weight[cnt] = w; // 边的权重是w
        head[u] = cnt++;
    }

    // 打印试图
    private static void printGraph(int n) {
        for (int i = 1; i <= n; i++) {
            System.out.print(i + "(邻居、边权) : ");
            // 注意这个for循环，链式前向星的方式遍历
            for (int ei = head[i]; ei > 0; ei = next[ei]) {
                System.out.print("(" + to[ei] + "," + weight[ei] + ") ");
            }
            System.out.println();
        }
    }
}
